package tree;

/**
 * @author wujun
 * @date 17-11-24.
 */
public class Solution99 {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "val: " + val;
        }
    }

    TreeNode prevNode = new TreeNode(Integer.MIN_VALUE);
    TreeNode firstNode;
    TreeNode secondNode;

    public void recoverTree(TreeNode root) {
        recursiveRecoverTree(root);
        System.out.println(firstNode);
        System.out.println(secondNode);

        int valTemp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = valTemp;
    }

    private void recursiveRecoverTree(TreeNode root) {
        if (root == null) {
            return;
        }

        recursiveRecoverTree(root.left);

        if (prevNode.val > root.val && firstNode == null) {
            firstNode = prevNode;
        }

        if (firstNode != null && prevNode.val > root.val) {
            secondNode = root;
        }

        prevNode = root;

        recursiveRecoverTree(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode left = new TreeNode(1);
        root.left = left;

        new Solution99().recoverTree(root);
    }
}
